#include <stdio.h>
#include <cstdlib>
#include <cstring>

//#2.2编程题练习P19#
typedef int ElemType;
typedef struct{
    ElemType data[50];
    int length;
}SqList;
//------------------------------------------------------------------
//第一题-删除元素
/*问题：1、顺序表所在的库是什么？2、类似break退出运行的函数怎么用*/
int DeleteMin(SqList &L){
    if(L.length == 0){
        printf("顺序表为空");
        exit(1);
    }
    int min = L.data[0]; // 初始化为第一个元素
    int index = 0;
    for(int i = 0;i < L.length;i++){
        if(L.data[i] < min){
            min = L.data[i];
            index = i;
        }
    }
    L.data[index] = L.data[L.length-1];
    L.length--;
    return min;
}
//------------------------------------------------------------------
//第二题:元素逆置
void Reserve(SqList &L){
    int begin = 0;
    int rear = L.length - 1;
    while (begin < rear){
        int temp = L.data[begin];
        L.data[begin] = L.data[rear];
        L.data[rear] = temp;

        begin++;
        rear--;
    }
}
//------------------------------------------------------------------
//第三题：删除所有指定元素
//原代码
void DeleteIndexes_alpha(SqList &L,int x){
    int last = L.length-1;//尾指针，总是指向数列最后一个元素
    for(int i = 0;i < L.length;i++){
        if(L.data[i] == x){
            //执行删除操作
            /*将这个值放到最后去，然后length减一
             * 如果直接执行删除操作的话，对于连着的两个需要删除的元素会只删去一个*/
            int num = L.data[last];
            L.data[last] = L.data[i];
            L.data[i] = num;
            last--;
            L.length--;
        }
    }
}
/*你的代码思路是正确的，可以满足题目要求的时间复杂度O(n)和空间复杂度O(1)，但在实现细节上有一个小问题需要修正。

主要问题：

在交换元素后，你需要重新检查当前位置i的新值（因为交换过来的可能是另一个需要删除的元素）

循环条件应该是i <= last而不是i < L.length，因为last之后的元素已经是处理过的*/
//修改后
void DeleteIndexes_1(SqList &L, int x) {
    int last = L.length - 1; // 尾指针，指向当前最后一个未处理的元素
    for (int i = 0; i <= last;) { // 注意循环条件
        if (L.data[i] == x) {
            // 交换当前元素和最后一个未处理的元素
            L.data[i] = L.data[last];
            last--;
            L.length--; // 顺序表长度减1
            // 这里不需要i++，因为交换过来的新元素还需要检查
        } else {
            i++; // 只有当前元素不需要删除时才移动i
        }
    }
}
//思路：设置头尾两个指针，从两端向中间移动，在遇到最左端x的元素时，直接将最右端非x的元素左移至值为x的元素位置，直至两指针相遇。但是这种方法会改变元素相对位置

//方法2：用k记录顺序表中不等于x的元素个数（需要保存的元素个数），扫描时将不等于x的元素移动至下标k的位置，并更新k值。扫描结束后修改L的长度
void DeleteIndexes_2(SqList &L,int x){
    int k = 0;
    for(int i = 0;i < L.length;i++){
        if(L.data[i] != x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}
//方法3：用k记录顺序表L中等于x的元素个数，一边扫描L，一边统计k，并将不等于x的元素前移k个位置。扫描结束后修改L的长度
void DeleteIndexes_3(SqList &L,int x){
    int k = 0,i = 0;
    while(i < L.length){
        if(L.data[i] == x){
            k++;
        } else{
            L.data[i-k] = L.data[i];
        }
        i++;
    }
    L.length = L.length - k;
}
//思考：在对顺序表中的元素执行删除操作时，将删除位置之后的所有元素前移太麻烦了。一般都是将需要删除的元素移到末尾，然后直接改变顺序表的长度即可

//------------------------------------------------------------------
//第四题：删除一定范围内的值
bool DeleteScope(SqList &L,int s,int t){
    int k = 0;//记录在s与t之间元素的个数
    if(s > t || L.length <= 0){
        printf("Wrong Parameter\n");
        return false;
    }
    for(int i = 0;i < L.length;i++){
        if((L.data[i] >= s) && (L.data[i] <= t)){
            k++;
        }else{
            L.data[i-k] = L.data[i];
        }
    }
    L.length = L.length - k;
    return true;
}

//------------------------------------------------------------------
//第五题：删除有序表中的重复值
void DeleteRepeat_alpha(SqList &L){
    int k = 0;//用k表示重复值的个数,用index表示指针
    for(int i  = 0;i < L.length;i++){
        if(L.data[i] == L.data[i-1]){
            k++;
        }
        L.data[i-k] = L.data[i];
    }
    L.length = L.length - k;
}
//主要错误：
/*数组越界访问（严重错误）：

在循环的第一次迭代（i = 0）时，条件判断 L.data[i] == L.data[i-1] 会访问 L.data[-1]。
数组索引从0开始，-1 是无效索引，这会导致未定义行为（程序崩溃或数据损坏）。这是典型的边界处理错误。

逻辑缺陷（即使修复越界）：

假设修复越界（如将循环改为 for(int i = 1; i < L.length; i++)），代码逻辑仍然不健壮：
k 被用作重复计数，但赋值 L.data[i-k] = L.data[i] 在每次迭代都执行，这可能导致不必要的覆盖（尽管在有序表下部分情况能工作，但依赖巧合）。
当表为空（L.length = 0）或只有一个元素时，循环行为未妥善处理（原始代码会越界）。
算法效率不高：每次迭代都进行赋值，而标准算法只在必要时赋值。*/
//修改
void DeleteRepeat(SqList &L) {
    if (L.length == 0)
        return; // 处理空表，避免无效操作
    int k = 1; // 新索引指针，从1开始（因为第一个元素必定保留）
    for (int i = 1; i < L.length; i++) { // 从第二个元素开始遍历
        if (L.data[i] != L.data[i-1]) { // 当前元素与前一个不重复
            L.data[k] = L.data[i]; // 复制到新位置
            k++; // 新索引后移
        }
    }
    L.length = k; // 更新表长
}
//方法2：使用插入排序的思想初始时将第一个元素视为非重复的有序表，之后以此判断后面的元素是否与前面非重复的有序表的最后一个元素相同。相同则继续向后，不同则插入前面的非重复有序表
bool DeleteRepeat2(SqList &L) {
    if (L.length == 0) {
        return false;
    }
    int i, j;/*i存储第一个不同的元素，j为工作指针*/
    for (i = 0, j = 1; j < L.length; j++) {
        if (L.data[i] != L.data[j]) {
            i++;
            L.data[i] = L.data[j];
        }
    }
    L.length = i + 1;
    return true;
}
//------------------------------------------------------------------
//第六题：合并两个有序顺序表
//代码解释：
/*初始化指针：

p1 指向 nums1 的最后一个有效元素（索引 m - 1）。

p2 指向 nums2 的最后一个元素（索引 n - 1）。

p 指向 nums1 的最后一个位置（索引 m + n - 1）。

从后向前比较并合并：

比较 nums1[p1] 和 nums2[p2]，将较大的元素放入 nums1[p]。

移动相应的指针（p1 或 p2）和 p 向前。

处理剩余元素：

如果 nums2 中还有剩余元素（即 p2 >= 0），直接将这些元素复制到 nums1 的前面。*/
//这是空间复杂度为O(1)的做法
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = m - 1;      // nums1的最后一个有效元素
    int p2 = n - 1;      // nums2的最后一个元素
    int p = m + n - 1;   // nums1的最后一个位置

    // 从后向前比较并合并
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // 如果nums2还有剩余元素，直接复制到nums1的前面
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}
//------------------------------------------------------------------
//第七题：交换一个顺序表中两块区域的位置
/*先写一个逆置一段顺序表的函数,使用双指针逆置。arraySize是数组长度*/
void Reserve(int A[],int left,int right,int arraySize){
    if(left >= right || right >=arraySize){
        return;
    }
    int mid = (left + right)/2;
    for(int i = 0;i <= mid - left;i++){
        int tmp = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = tmp;
    }
}
/*正式解题代码*/
void Exchange(int A[],int m,int n,int arraySize){
    Reserve(A,0,m+n-1,arraySize);
    Reserve(A,0,n-1,arraySize);
    Reserve(A,n,m+n-1,arraySize);
}
//------------------------------------------------------------------
//第八题：寻找指定元素并交换/插入
void SearchExchangeInsert(int A[],int x,int length){
    /*C语言不能通过函数来获取数组长度*/
    int low = 0,high = length - 1,mid;
    while (low <= high){
        mid = (low + high) / 2;
        if(A[mid] == x){
            printf("had Found");
            break;
        }else if(A[mid] < x){
            low = mid + 1;
        } else{
            high = mid - 1;
        }
    }
    if(A[mid] == x && mid != length - 1){
        int temp = A[mid];
        A[mid] = A[mid + 1];
        A[mid + 1] = temp;
    }
    if(low > high){
        printf("hadn't Found,need Insert");
        for(int i = length - 1;i > high;i--){
            A[i+1] = A[i];
        }
        A[low] = x;
    }
}
//------------------------------------------------------------------
//第十二题：寻找主元素
//算法核心思想
/*目标：找到数组中出现次数超过 n/2 的元素（主元素）。
关键观察：
如果存在主元素，它的出现次数比其他所有元素的总和还要多。
通过“投票”和“抵消”的方式，最终剩下的候选元素可能是主元素（需验证）。*/
int FindMajorityElement(int A[], int n) {
    // 第一遍扫描：找出候选主元素
    int candidate = A[0], count = 1;
    for (int i = 1; i < n; i++) {
        if (count == 0) {
            candidate = A[i];
            count = 1;
        } else if (A[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // 第二遍扫描：验证候选是否为主元素
    count = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] == candidate) {
            count++;
        }
    }
    return (count > n / 2) ? candidate : -1;
}
//------------------------------------------------------------------
//第十三题：寻找未出现的最小正整数（标记法）
/*使用数组B标记在数组A中出现过的元素，对于不大于0和大于n的元素不做处理，数组B初始值为0
 * 例如A[0] = 2，就将B[2] = 1，表示2已经出现过。
 * 对于1~n中未出现过的数，B中对应下标元素为0，若1~n都出现过，那么未出现的最小正整数就是n+1*/
int FindMissMin(int A[],int n){
    int i;
    int *B = (int*) malloc(n * sizeof (int ));//这样新建数组并分配动态空间
    memset(B,0,sizeof (int) * n);//初始赋值为0
    for(int i = 0;i < n;i++){
        if(A[i] > 0 && A[i] < n){
            B[A[i] - 1] = 1;
        }
    }
    for(int i = 0;i < n;i++){
        if(B[i] == 0){
            break;
        }
    }
    return i+1;
}
//------------------------------------------------------------------

//打印顺序表
void PrintList(SqList &L){
    for(int i = 0;i < L.length;i++){
        printf("%d ",L.data[i]);
    }

    printf("\n");
}

int main() {
    /*SqList list = {{2,3, 2,1, 4, 2, 5,2,},8}; // 初始化顺序表*/
    //能这样初始化顺序表吗？
    /*int min = DeleteMin(list);
    printf("删除的最小值是: %d\n", min);
    printf("删除后的顺序表长度: %d\n", list.length);
    return 0;*/
    //以上是第一题的测试代码
    /*PrintList(list);
    DeleteIndexes_2(list,2);
    PrintList(list);*/
    //以上是第三题的测试代码
    /*PrintList(list);
    DeleteScope(list,1,3);
    PrintList(list);*/
    //以上是第四题的测试代码
    /*SqList list = {{1,2,2,2,3,3,4,4,5,6,6,6},12};
    PrintList(list);
    DeleteRepeat(list);
    PrintList(list);*/
    //以上是第五题的测试代码
    /*int A[] = {5,4,3,2,1,9,8,7,6};
    Exchange(A,5,4,9);
    for(int i = 0;i < 9;i++){
        printf("%d ",A[i]);
    }*/
    //以上是第七题的测试代码
    /*int A[] = {1,2,4,5,6,7,8,9};
    for(int i = 0;i < 8;i++){
        printf("%d ",A[i]);
    }
    printf("\n");
    SearchExchangeInsert(A,10,9);
    printf("\n");
    for(int i = 0;i < 9;i++){
        printf("%d ",A[i]);
    }*/
    //以上是第八题的测试代码
    int A1[] = {0, 5, 5, 3, 5, 7, 5, 5};
    int n1 = sizeof(A1) / sizeof(A1[0]);
    printf("主元素: %d\n", FindMajorityElement(A1, n1)); // 输出: 5

    int A2[] = {0, 5, 5, 3, 5, 1, 5, 7};
    int n2 = sizeof(A2) / sizeof(A2[0]);
    printf("主元素: %d\n", FindMajorityElement(A2, n2)); // 输出: -1
    //以上是第十二题的测试代码
    return 0;
}
